/**
 * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 * 最小深度
 * @param root 
 */
const minDepth = (root: TreeNode | null): number => {
    // 树为空
    if (root === null) return 0
    let ans = 0,
        queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const len = queue.length;

        // 遍历队列的所有节点
        for (let i = 0; i < len; i++) {
            // 从第一项一个个弹出节点
            const n = queue.shift()!;
            // 只要遍历到的节点是叶子节点, 就返回
            if (n.left == null && n.right === null) return ans + 1;

            // 放入左节点
            if (n.left !== null) queue.push(n.left)

            // 放入右节点
            if (n.right !== null) queue.push(n.right);
        }
        // 没有叶子节点, 深度加1
        ans++;
    }
    // 不会走到这
    return ans
};

// 递归
const minDepth2 = (root: TreeNode | null): number => {
    // 树为空
    if (root === null) return 0


    /**
     * 求最小深度
     * @param n 
     */
    const depth = (n: TreeNode | null): number => {
        if (n === null) return 0;

        // 求左边
        const l = depth(n.left);

        // 求右边
        const r = depth(n.right);

        // 是叶子节点
        if (l !== 0 && r === 0) {
            // 只有左孩子
            return l + 1
        } else if (l === 0 && r !== 0) {
            // 只有右孩子
            return r + 1
        } else if (l === 0 && r === 0) {
            return 1;
        } else {

            return Math.min(l, r) + 1
        }
    }

    return depth(root);
};